package number_operatation.leetcode.easy;

import java.util.Arrays;

/**
 * @author bruin_du
 * @description 只出现一次的数字
 * @date 2022/8/1 20:29
 **/
public class OfferII004_SingleNumber {
    public int singleNumber(int[] nums) {
        //方法一:排序遍历
        method1(nums);

        //方法二:有限状态自动机
        method2(nums);

        //方法三:遍历每一比特位除相同的个数
        return method3(nums);
    }

    private int method1(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i+=3) {
            if (!(nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2])) {
                return nums[i] ^ nums[i + 1] ^ nums[i + 2];
            }
        }
        return nums[nums.length - 1];
    }

    private int method2(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = ones ^ num & (~twos);
            twos = twos ^ num & (~ones);
        }
        return ones;
    }

    private int method3(int[] nums) {
        int[] arr = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                //与1相与才符合要求，num无符号右移
                arr[i] += (1 & num);
                num >>>= 1;
            }
        }
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            arr[i] %= 3;
            res |= (arr[i] << i);
        }
        return res;
    }
}
